def compress(uncompressed):
    dict_size = 256
    dictionary = dict((chr(i), chr(i)) for i in xrange(dict_size))
    
    w = ""
    result = []
    for c in uncompressed:
        wc = w + c
        if wc in dictionary:
            w = wc
        else:
            result.append(dictionary[w])
            dictionary[wc] = dict_size
            dict_size += 1
            w = c
    if w:
        result.append(dictionary[w])
    return result 
 
def decompress(compressed):
    dict_size = 256
    dictionary = dict((chr(i), chr(i)) for i in xrange(dict_size))
    
    w = result = compressed.pop(0)
    for k in compressed:
        if k in dictionary:
            entry = dictionary[k]
        elif k == dict_size:
            entry = w + w[0]
        else:
            raise ValueError('Bad compressed k: %s' % k)
        result += entry
 
        # Add w+entry[0] to the dictionary.
        dictionary[dict_size] = w + entry[0]
        dict_size += 1
 
        w = entry
    return result
 
def pack(compressed):
    ba = bytearray()
    for i,x in enumerate(compressed):
        if isinstance(x,str): x = ord(x)
        if i%2==0:
            ba.extend(((x>>4)&255,x&15))
        else:
            ba[-1]=(ba[-1]<<4)+((x>>8)&15)
            ba.append(x&255)
    return str(ba)

def unpack(compressed):
    lst = []
    for i, x in enumerate(compressed):
        x = ord(x)
        if i%3 == 0:
            lst.append(x)
        elif i%3 == 1:
            lst[-1] = (lst[-1]<<4)+((x>>4)&15)
            if i != (len(compressed)-1):
                if lst[-1]<256: lst[-1]=chr(lst[-1])
                lst.append(x&15)
            else:
                lst[-1] = lst[-1]+(x&15) 
        else:
            lst[-1] = (lst[-1]<<8)+x
            if lst[-1]<256: lst[-1]=chr(lst[-1])
    return lst

def encode_file(inputname, outputname):
    msg = open(inputname,'rb').read()
    t = compress(msg)
    open(outputname,'wb').write(pack(t))

def decode_file(inputname, outputname):
    msg = open(inputname,'rb').read()
    t = unpack(msg)
    open(outputname,'wb').write(decompress(t))
